package Day_0220.Redis;

/**
 * @author zxc
 * @date 2023/02/20 20:10
 **/
public class Bloon_Filter {
    public static void main(String[] args) {
        /**
         * 谈一谈对于布隆过滤器的理解
         * ===》
         * 一，恶意流量穿透
         * 1.假设我们的Redis里存有一组用户的注册email，以email作为Key存在，同时它对应着DB里的User表的部分字段。
         * 2.一般来说，一个合理的请求过来，会先在Redis里判断这个用户是否是会员，因为从缓存里读数据返回快。
         * 如果这个会员在缓存中不存在那么我们会去DB中查询一下。
         *
         * 3.恶意流量穿透的案例 ：
         * 有千万个不同IP的请求，带着Redis && 数据库中皆不存在的key，来访问你的网站 ：
         * （1）请求到达Web服务器；
         * （2）请求派发到应用层 -> 微服务层；
         * （3）请求去Redis捞数据，Redis内不存在这个Key；
         * （4）于是请求到达DB层，在DB建立connection后进行一次查询
         * ===》
         * 千万乃至上亿的DB连接请求（高并发情况下），先不说Redis是否撑的住，DB也会被瞬间打爆。
         * 这就是“Redis穿透”，它会打爆你的缓存 / 是连DB一起打爆进而引起一系列的“雪崩效应”。
         *
         * 二，布隆过滤器
         * 1. 含义
         * （1）布隆过滤器（Bloom Filter）是由Howard Bloom在1970年提出的一种比较巧妙的概率型数据结构，
         *  它实际上是由一个很长的二进制(0或1)向量和一系列随机映射函数组成。
         * （2）布隆过滤器可以用于，检索一个元素是否在一个集合中。
         *  它可以告诉你某种东西一定不存在或者可能存在。
         *  当布隆过滤器说，某种东西存在时，这种东西可能不存在；当布隆过滤器说，某种东西不存在时，那么这种东西一定不存在。
         *  ===》
         *  即，bloom filter（布隆过滤器）能够返回 某些所要查询的数据 可能存在/一定不存在的情况;
         *
         * （3）布隆过滤器优点：
         *  A. 空间效率高，占用空间少
         *  B. 查询时间短
         * （4）缺点：
         *  A. 有一定的误判率
         *  B. 元素不能删除
         *
         * 2. bloom filter原理
         * （1）当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点
         * （使用多个哈希函数对元素key (bloom中不存value) 进行哈希，算出一个整数索引值，
         *  然后对位数组长度进行取模运算得到一个位置，每个无偏哈希函数都会得到一个不同的位置），把它们置为1。
         *
         * （2）检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：
         *  a.如果这些点有任何一个为0（如下图的e），则被检元素一定不在；
         *  b.如果都是1（如下图的d），并不能完全说明这个元素就一定存在其中，
         *  有可能这些位置为1是因为其他元素的存在，这就是布隆过滤器会出现误判的原因。
         *
         * （3）补充：
         *  Bloom Filter跟 ‘’单哈希函数BitMap‘’ 不同之处在于：
         *  Bloom Filter使用了k个哈希函数，每个字符串跟k个bit对应，从而降低了冲突的概率。
         * ===》
         * （1）即，bloom filter使用k种哈希函数，将集合中所有数据进行k次哈希运算，
         *  即集合中每个元素都由k个哈希位置（bit）组成，极大程度上减少了哈希冲突发生的概率。
         * （2）若是某个值经过k中哈希函数运算之后，所得到的k个哈希位置（bit） ：
         *  a.若是k个哈希位置中，有0存在的话，则代表该元素必然不属于集合中;
         *  b.但若是k个哈希位置中，没有0出现的话，也并不代表该元素必然在集合中;
         *
         * 3.bloom filter（布隆过滤器）的实现
         * （1）Redis的bitmap
         *  基于redis的 bitmap数据结构 的相关指令来执行。
         * （2）RedisBloom （推荐）
         *  布隆过滤器可以使用Redis中的位图(bitmap)操作实现，直到Redis4.0版本提供了插件功能，
         *  Redis官方提供的布隆过滤器才正式登场，布隆过滤器作为一个插件加载到Redis Server中，
         *  官网推荐了一个RedisBloom 作为 Redis 布隆过滤器的 Module。
         * （3）PyreBloom
         *  pyreBloom 是 Python 中 Redis + BloomFilter 模块，是c语言实现。
         *  如果觉得Redis module的形式部署很麻烦或者线上环境Redis版本不是 4.0 及以上，则可以采用这个，
         *  但是它是在 hiredis 基础上，需要安装hiredis，且不支持重连和重试。
         * （4）Lua脚本实现
         * （5）guvua包自带的布隆过滤器
         *
         *
         * 4.Bloom Filter 应用场景
         * 1）解决缓存穿透
         * （1）含义
         * 业务请求中数据缓存中没有，DB中也没有，导致类似请求直接跨过缓存，反复在DB中查询，与此同时缓存也不会得到更新。
         * （2）缓存穿透的解决思路
         *  事先把存在的key都放到redis的Bloom Filter 中，用途就是存在性检测，
         *  如果 BloomFilter 中不存在，那么数据一定不存在；如果 BloomFilter 中存在，实际数据也有可能会不存在。
         * 剖析 ：布隆过滤器可能会误判，放过部分请求，当不影响整体，所以目前该方案是处理此类问题最佳方案。
         *
         * 2）黑名单校验
         *  识别垃圾邮件，只要发送者在黑名单中的，就识别为垃圾邮件。
         *  假设黑名单的数量是数以亿计的，存放起来就是非常耗费存储空间的，布隆过滤器则是一个较好的解决方案。
         *  把所有黑名单都放在布隆过滤器中，再收到邮件时，判断邮件地址是否在布隆过滤器中即可。
         *
         * ps：
         * 如果用哈希表，每存储一亿个 email地址，就需要 1.6GB的内存
         * ===》
         * 用哈希表实现的具体办法是
         * （1）将每一个 email地址对应成一个八字节的信息指纹，
         * （2）然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有 50%，因此一个 email地址需要占用十六个字节。
         * （3）一亿个地址大约要 1.6GB，即十六亿字节的内存）。
         *  因此存贮几十亿个邮件地址可能需要上百 GB的内存。
         *  而Bloom Filter只需要哈希表 1/8到1/4 的大小就能解决同样的问题。
         *
         *  ===>
         *  总结 ：
         *  （1）黑名单实现，即将统计的黑名单发送者记录全部存储到bloom filter中去
         *  （2）若是有某个邮件发送者 进行邮件发送服务的话，
         *   若是在bloom filter中未能够匹配到该发送者信息的话，则代表该发送者必然不是黑名单所记录下来的发送者;
         *   若是在bloom filter中匹配到该发送者信息的话，则代表该发送者有可能是黑名单中所记录下来的发送者
         *
         * 3. Web拦截器
         * （1）含义
         *  如果相同请求则拦截，防止重复被攻击。
         * （2）解决思路
         *  用户第一次请求，将请求参数放入布隆过滤器中，
         *  当第二次请求时，先判断请求参数是否被布隆过滤器命中，从而提高缓存命中率。
         *
         *  ===》
         *  总结
         *  （1）即，在客户端/浏览器 和 服务器之间增加一个bloom filter，
         *  （2）当客户端第一次像服务器发送请求时，则将该请求参数加入到bloom filter中，
         *  （3）当客户端发送重复请求的话，则选择去bloom filter中去判断该请求是否已经存在，
         *   若是该请求参数不存在的话，则将该请求进行放行;
         *   若是该请求参数存在的话，则该请求有可能是在之前已经发送过的;
         *
         * 5.布隆过滤器其他场景
         * 1、原本有10亿个号码，现在又来了10万个号码，要快速准确判断这10万个号码是否在10亿个号码库中？
         * （1）数据库查询 ：
         *  将10亿个号码存入数据库中，进行数据库查询，准确性有了，但是速度会比较慢。
         * （2）redis缓存查询 ：
         *  将10亿号码放入内存中，比如，Redis缓存中，这里我们算一下占用内存大小：
         *  10亿 * 8字节 = 8GB，通过内存查询，准确性和速度都有了，
         *  但是大约8gb的内存空间，挺浪费内存空间的。
         *  ===》
         *  即，由于bloom filter所使用的是位数组，来存储每个元素值在bloom filter中所对应的值集合;
         *  bloom filter所使用内存大小，取决于bloom filter中位数组大小;
         *
         * 2、接触过爬虫的，应该有这么一个需求，需要爬虫的网站千千万万，
         * 对于一个新的网站url，我们如何判断这个url我们是否已经爬过了？
         * 3、还有垃圾邮箱的过滤。
         *
         * ===>
         * 大数据量集合，如何准确快速的判断某个数据是否在大数据量集合中，并且不占用内存
         * ===> 布隆过滤器
         *
         */
    }
}
